1. Field of the Invention
This invention relates to the analysis of digital images, specifically to the construction of computational meshes from such images.
2. Description of the Prior Art
Digital images are often analyzed to obtain meshes for further computation. For example, seismic images are analyzed to obtain geologic meshes used to simulate oil flowing in subsurface reservoirs. Similarly, medical images of the human brain are analyzed to obtain meshes used to simulate blood flow in arteries. A somewhat different example is image morphing, in which meshes derived from one image may be used to encode efficiently differences in subsequent images. In all of these applications, an image is analyzed to construct a mesh.
Images and Meshing Today
Specifically, such applications often consist of the following sequence of steps:
(1) Process an image to enhance features of interest.
(2) Find curves or surfaces in the image that bound regions of interest.
(3) Fill the space defined by those regions with a computational mesh.
(4) Simulate some process on the space-filling mesh.
For an application in medical imaging, see, Cebral, J. R., and Lxc3x6hner, R., From Medical Images to CFD Meshes, Proceedings of the 8th International Meshing Roundtable, p. 321-331, Sandia, 1999. For an application in seismic imaging, see, Garrett, S., Griesbach, S., Johnson, D., Jones, D., Lo, M., Orr, W., and Sword, C., Earth Model Synthesis, First Break, v. 15, no. 1, p. 13-20, 1997.
For various reasons, each step in this sequence is today often taken independently, with little regard for the requirements of subsequent steps. For example, it is common in step (2) to produce a bounding curve or surface with more detail than can be represented in the space-filling mesh used in step (4). Seismic reflections representing geologic interfaces are routinely mapped with higher resolution than can practically be used in meshes for petroleum reservoir simulation. This leads to the xe2x80x9cscale upxe2x80x9d or xe2x80x9cupscalingxe2x80x9d problem cited by Garrett et al. (1997).
This discrepancy in resolution is often accompanied by a discrepancy in data structure. For example, a two-dimensional (2-D) curve represented by a simple linked list of line segments in step (2) may become a relatively complex mesh of triangles in step (3). Such discrepancies today disrupt the analysis sequence, and may yield inconsistencies between the image processed in step (1) and the mesh used in step (4) that are difficult to quantify.
The disruptions are costly. In the example of seismic image analysis, one iteration of this sequence today may require months of work. This high cost makes it difficult to perform multiple iterations in an attempt to estimate uncertainties in analysis results.
One reason for discrepancies in resolution and data structure lies in the implementation of the analysis sequence. Historically, the four steps listed above may have been performed by separate computer programs, developed independently, and used by different specialists. Today, a single person or small group may perform all four steps in this sequence, and there exists demand for the steps to be more integrated.
Another reason for discrepancies is a lack of methodology. The simulation step (4) often requires the numerical solution of partial differential equations (PDEs). In the past, these solutions were feasible for only structured meshes, in which mesh elements can be indexed as simple arrays. The conversion of an unstructured mesh produced in step (3) to a structured mesh yields additional inconsistencies between the processed image and the mesh used in simulation. However, recent advances in numerical methods for solving PDEs on unstructured meshes suggest that this conversion and resulting inconsistencies can be avoided.
Meshing with Lattices
The accuracy of most computations performed on meshes depends on the regularity of mesh elements. Simulations performed on highly regular triangular meshes, those with nearly equilateral triangles, are more accurate than those performed on irregular meshes with long thin triangles.
This is one reason that the Delaunay triangulation is popular. Given a set of points representing the locations of nodes for a 2-D mesh, the Delaunay triangulation of those points, when compared with all other possible triangulations, yields triangles most nearly equilateral. However, Delaunay triangulation alone does not guarantee a regular mesh. For that, one must choose carefully the locations of the mesh nodes.
(For a survey of 2-D and 3-D Delaunay triangulation applied to the problem of meshing, see Bern, M., and Eppstein, D., Mesh Generation and Optimal Triangulation, in Computing in Euclidean Geometry, Du, D. -Z. and Hwang., F. K. eds., World Scientific, 1995.)
Outside the domain of image analysis, the problem of choosing optimal mesh node locations has been well studied. One solution to this problem is based on the observation that the triangulation of a set of points defined by a simple crystal lattice yields a highly regular mesh. (See Mello, U. T., and Cavalcanti, P. R., A Point Creation Strategy for Mesh Generation Using Crystal Lattices as Templates, Proceedings of the 9th International Meshing Roundtable, p. 253-261, Sandia, 2000.) However, a uniform lattice of points can seldom be aligned exactly with the boundaries of objects to be meshed. Therefore, some solutions begin with an approximately uniform lattice, and then use numerical models of physical forces between atoms or bubbles to automatically move mesh nodes (atoms or bubbles) to more optimal locations. (See Shimada, K., Physically-Based Mesh Generation: Automated Triangulation of Surfaces and Volumes via Bubble Packing, Ph.D. thesis, Massachusetts Institute of Technology, 1993, and Shimada, K., and Gossard, D. C., Bubble Mesh: Automated Triangular Meshing of Non-Manifold Geometry by Sphere Packing, in Proceedings of the Third Symposium on Solid Modeling and Applications, p. 409-419, 1995. U.S. Pat. No. 6,124,857, to Itoh, T., Inoue, K., Yamada, A., and Shimada, K., Meshing Method and Apparatus, 2000, extends this work to quadrilateral meshing. See also Bossen, F. J., and Heckbert, P. S., A Pliant Method for Anisotropic Mesh Generation, Proceedings of the 5th International Meshing Roundtable, p. 63-74, Sandia, 1996.)
In all of these examples, lattice-based meshing begins with a geometric model that defines precisely the internal and external boundaries of objects to be meshed. Thus, there exists a need for a meshing system and methodology capable of addressing problems where such boundaries may not be known a-priori.
U.S. Patents Cited in this Specification
U.S. Pat. No. 4,908,781, to Levinthal, C., and Fine, R., Computing Device for Calculating Energy and Pairwise Central Forces of Particle Interactions, 1990.
U.S. Pat. No. 5,596,511, to Toyoda, S., Ikeda, H, Hashimoto, E., and Miyakawa, N., Computing Method and Apparatus for a Many-Body Problem, 1997.
U.S. Pat. No. 6,124,857, to Itoh, T., Inoue, K., Yamada, A., and Shimada, K., Meshing Method and Apparatus, 2000.
Other References Cited in this Specification
Bentley, J. L., and Friedman, J. H., Data Structures for Range Searching, Computing Surveys, vol. 11, no. 4, 1979.
Bern, M., and Eppstein, D., Mesh Generation and Optimal Triangulation, in Computing in Euclidean Geometry, Du, D. -Z. and Hwang., F. K. eds., World Scientific, 1995.
Bossen, F. J., and Heckbert, P. S., A Pliant Method for Anisotropic Mesh Generation, Proceedings of the 5th International Meshing Roundtable, p. 63-74, Sandia, 1996.
Byrd, R. H., Nocedal, J., and Schnabel, R. B., Representations of Quasi-Newton Matrices and Their Use in Limited Memory Methods, Technical Report NAM-03, Northwestern University, Department of Electrical Engineering and Computer Science, 1996.
Cebral, J. R., and Lxc3x6hner, R., From Medical Images to CFD Meshes, Proceedings of the 8th International Meshing Roundtable, p. 321-331, Sandia, 1999.
Garrett, S., Griesbach, S., Johnson, D., Jones, D., Lo, M., Orr, W., and Sword, C., Earth Model Synthesis, First Break, v. 15, no. 1, p. 13-20, 1997.
Mello, U. T., and Cavalcanti, P. R., A Point Creation Strategy for Mesh Generation Using Crystal Lattices as Templates, Proceedings of the 9th International Meshing Roundtable, p. 253-261, Sandia, 2000.
Shimada, K., Physically-Based Mesh Generation: Automated Triangulation of Surfaces and Volumes via Bubble Packing, Ph.D. thesis, Massachusetts Institute of Technology, 1993.
Shimada, K., and Gossard, D. C., Bubble Mesh: Automated Triangular Meshing of Non-Manifold Geometry by Sphere Packing: Proceedings of the Third Symposium on Solid Modeling and Applications, ACM Press, p. 409-419, 1995.
In accordance with various embodiments of this invention, a method for generating a lattice of points which respects features in a digital image comprises a process for initializing a lattice, and a process for optimizing the alignment of that lattice with respect to the image features. The optimization process operates by adjusting points of the lattice to extremize a composite function of the spatial coordinates of the lattice points. The composite function may be a weighted combination of a first function of pair-wise distances between the points, and a second function derived from the image (e.g., computed from sampled values of the image near the lattice points).
A mesh may be generated from the optimized lattice. The mesh may be used in any of a variety of applications. For example, the mesh may be used to simulate a process associated with the image. As another example, the mesh may be used to compress the image or subsequent images in an image sequence (e.g. a video stream).
In some embodiments, the optimized lattice may be used to encode information associated with the image with or without the generation of an intermediate mesh. Any of various types of associated information are contemplated.
Objects and Advantages
One object of at least some embodiments of this invention is a method that enables one to replace the image analysis sequence described above (in the description of the prior art) with the more efficient sequence:
(1) Process an image to enhance features of interest.
(2) Fill space with a computational mesh aligned with image features.
(3) Simulate some process on the space-filling mesh.
Instead of finding boundaries of regions within images and then meshing those regions, one simply constructs a mesh that is aligned with the boundaries.
Additional objects of some embodiments of this invention are the use of this method to construct:
highly regular meshes, suitable for further computations, such as the solution of partial differential equations; and
graded meshes, in which the density of mesh nodes varies with image complexity or a user-specified function; and
3-D meshes, where 3-D images are available.
These and other objects and advantages of various embodiments of the invention will become apparent from consideration of the following description and drawings.